package club.xiaojiawei.monotonestack;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/9/22 6:36 PM
 * @question 739. 每日温度
 * @description 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 */
public class DailyTemperatures739 {

    public static void main(String[] args) {
        DailyTemperatures739 test = new DailyTemperatures739();
        int[] result = test.dailyTemperatures2(new int[]{73,74,75,71,69,72,76,73});
        System.out.println(Arrays.toString(result));
    }

    /**
     * 栈
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<int[]> stack = new Stack<>();
        int[] result = new int[temperatures.length];
        for (int i = temperatures.length - 1; i >= 0; i--) {
            if (stack.isEmpty()){
                result[i] = 0;
            }else if (temperatures[i] < stack.peek()[0]){
                result[i] = 1;
            }else {
                while (true){
                    if (stack.isEmpty()){
                        result[i] = 0;
                        break;
                    }else if (stack.peek()[0] > temperatures[i]){
                        result[i] = stack.peek()[1] - i;
                        break;
                    }else {
                        stack.pop();
                    }
                }
            }
            stack.push(new int[]{temperatures[i], i});
        }
        return result;
    }

    /**
     * 朴素法
     * 时间复杂度 O(mn)
     * 空间复杂度 O(m)
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures2(int[] temperatures) {
        int[] result = new int[temperatures.length];
        for (int i = temperatures.length - 2; i >= 0; i--) {
            if (temperatures[i] < temperatures[i + 1]){
                result[i] = 1;
            }else {
                int j = i + 1;
                while (true){
                    if (j >= temperatures.length){
                        result[i] = 0;
                        break;
                    }else if (temperatures[j] > temperatures[i]){
                        result[i] = j - i;
                        break;
                    }else {
                        j++;
                    }
                }
            }
        }
        return result;
    }

    /**
     * 官方-单调栈
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures3(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }

    /**
     * 民间-单调栈
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures4(int[] temperatures) {
        int[] res = new int[temperatures.length];
        for (int i = temperatures.length-2; i >= 0; i--) {
            int j = i + 1;
            while(true){
                if(temperatures[i] < temperatures[j]){
                    //如果右边的大于左边的那么确定j是i右边第一个大于它的温度
                    res[i] = j - i;
                    break;
                } else if(res[j] == 0){
                    //你前面的温度在右边找不到大于它的，所以对于你而言也必然找不到
                    res[i] = 0;
                    break;
                } else if(temperatures[i] == temperatures[j]){
                    //res[j] != 0，对于i前面的j而言已经找到右边第一个大于它的值
                    // (这个值对于i而言也是其右边第一个大于它的值，因为temperatures[i] == temperatures[j])
                    res[i] = res[j] + j - i;
                    break;
                } else {
                    //temperatures[i] > temperatures[j]，res[j] != 0
                    //更新 j 的值，往后找是否存在第一个大于j且大于i的值（循环必然会满足以上三个条件中的一个）
                    j += res[j];
                }
            }
        }
        return res;
    }

}
